package day11;

import java.util.Random;

public class SkipListExample {

    public static void main(String[] args) {
        SimpleSkipList list = new SimpleSkipList();
        assert list.isEmpty();
        list.add(20);
        list.add(22);
        list.add(55);
        System.out.println(list.get(20));
        assert list.size() == 3;
        assert list.contains(20);
        assert list.get(20) == 20;
    }
}

/**
 * 跳表的数据结构
 */
class SimpleSkipList {
    // 头部节点
    private Node head;
    // 尾部节点
    private Node tail;
    // 长度
    private int size;
    // 高度
    private int height;
    // 随机数，防止元素的位置
    private final Random random;
    // 每一层头部节点的标记符
    private final static byte HEAD_BIT = (byte) -1;
    // 每一层尾部节点的标记符
    private final static byte TAIL_BIT = (byte) 1;
    // 每一层数据节点的标记符
    private final static byte DATA_BIT = (byte) 0;

    public SimpleSkipList() {
        this.head = new Node(null, HEAD_BIT);
        this.tail = new Node(null, TAIL_BIT);
        this.head.right = tail;
        this.tail.left = head;
        this.random = new Random(System.currentTimeMillis());
    }

    public void add(Integer element) {
        // 获取位置，称为最近节点
        Node node = find(element);
        // 创建节点，称为新节点
        Node newNode = new Node(element);

        // 新节点定义链表的指针
        // 新节点的左边指向最近节点
        newNode.left = node;
        // 新节点的右边指向最近节点的右边
        newNode.right = node.right;

        // 最近节点定义链表的指针
        // 最近节点的右边节点，它的左边指向新节点
        node.right.left = newNode;
        // 最近节点的右边指向新节点
        node.right = newNode;

        // 新节点的层级
        int currentLevel = 0;
        // 根据跳表算法，计算新节点是否被放到新层.
        while (random.nextDouble() < 0.5d) {
            if (currentLevel >= height) {
                // 高度
                height++;
                // 新层高的头和尾
                Node dumyHead = new Node(null, HEAD_BIT);
                Node dumyTail = new Node(null, TAIL_BIT);
                // 新层头的右边指向新层尾
                dumyHead.right = dumyTail;
                // 新层头的下边指向头部节点
                dumyHead.down = head;
                // 头部节点的上边指向新层头
                head.up = dumyHead;
                // 同理
                dumyTail.left = dumyHead;
                dumyTail.down = tail;
                tail.up = dumyTail;
                head = dumyHead;
                tail = dumyTail;
            }
            // 新层次下，对原始节点也要维护
            while ((node != null) && node.up == null) {
                // 当node非null而且上边还有节点时，将最近节点替换为最近节点左边的节点
                node = node.left;
            }
            assert node != null;
            // 最近节点上边的节点替换最近节点，并对其进行更新操作。以下还称为最近节点
            node = node.up;
            // 创建新的上边指向的节点，称为上指向节点
            Node upNode = new Node(element);

            // 上指向节点的更新
            // 上指向节点的左边指向最近节点
            upNode.left = node;
            // 上指向节点的右边指向最近节点的右边。也就是在中间插入一个节点，将该新节点的右边更新为老节点右边的节点
            upNode.right = node.right;

            // 下指向节点的下边指向新节点
            upNode.down = newNode;

            // 最近节点的更新
            // 最近节点的右边的节点，它左边指向上指向节点
            node.right.left = upNode;
            // 最近节点的右指向为上指向节点
            node.right = upNode;
            // 新节点的上边指向上指向节点
            newNode.up = upNode;
            // 新节点赋值为上指向节点，因为这时候的所以上下左右的指向都已经更新结束了
            newNode = upNode;
            currentLevel++;
        }
        size++;
    }

    public boolean contains(Integer element) {
        Node node = this.find(element);
        return (node.value.equals(element));
    }

    public Integer get(Integer element) {
        Node node = this.find(element);
        return (node.value.equals(element)) ? node.value : null;
    }

    public boolean isEmpty() {
        return (size() == 0);
    }

    public int size() {
        return size;
    }

    /**
     * 寻找元素在哪个节点的附近，称为最近节点
     */
    private Node find(Integer element) {
        // 从头部开始
        Node current = head;
        // 循环查找
        for (; ; ) {
            // 如果右边元素不是头部节点而且值小于当前元素
            while (current.right.bit != TAIL_BIT && current.right.value <= element) {
                // 右移一位
                current = current.right;
            }
            // 如果下位非空，则下移
            if (current.down != null) {
                current = current.down;
            } else {
                break;
            }
        }
        return current;
    }

    private static class Node {
        private Integer value;
        // 上下左右的数据
        private Node up, down, left, right;
        // 节点类型
        private byte bit;

        public Node(Integer value) {
            this.value = value;
        }

        public Node(Integer value, byte bit) {
            this.value = value;
            this.bit = bit;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", bit=" + bit +
                    '}';
        }
    }
}
